package com.LeeCode;

import org.junit.jupiter.api.Test;

/**
 * 统计好数字的数目
 */

public class Code1922 {
    public static void main(String[] args) {

    }

    // 快速幂
    public int countGoodNumbers(long n) {
        long mod = 1_000_000_007;
        long evenPositions = (n + 1) / 2;  // 偶数位的数量
        long oddPositions = n / 2;         // 奇数位的数量

        // 计算 5^evenPositions * 4^oddPositions % mod
        long power5 = fastPow(5, evenPositions, mod);
        long power4 = fastPow(4, oddPositions, mod);
        return (int) ((power5 * power4) % mod);
    }

    // 快速幂计算 (base^power) % mod
    private long fastPow(long base, long power, long mod) {
        long result = 1;
        while (power > 0) {
            if (power % 2 == 1) {
                result = (result * base) % mod;
            }
            base = (base * base) % mod;
            power /= 2;
        }
        return result;
    }
}
